package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
字典序最小问题

给一个定长为N的字符串S,构造一个字符串T,长度也为N
起初，T是一个空串，随后反复进行下列任意操作

1. 从S的头部删除一个字符，加到T的尾部
2. 从S的尾部删除一个字符，加到T的尾部

目标是最后生成的字符串T的字典序尽可能小

1 ≤ N ≤ 2000
字符串S只包含大写英文字母

输入：字符串S
输出：字符串T

 */
public class d字典序最小by贪心 {
	public static void main(String[] args) {
		d字典序最小by贪心 test = new d字典序最小by贪心();
		test.useGreedyAlgorithmMinimumDictionaryOrder();
	}
	
	public void useGreedyAlgorithmMinimumDictionaryOrder() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			sb.append(scanner.next());
		}
		GreedyAlgorithmMinimumDictionaryOrder(sb.toString());
	}
	
	public void GreedyAlgorithmMinimumDictionaryOrder(String s) {
		String opposite = new StringBuilder(s).reverse().toString();
		int N = s.length();
		StringBuilder res = new StringBuilder();
		int count = 0;
		while (res.length() < N) {
			//哪个串的首字符字典序小，就用谁的charAt(0)
			if (s.compareTo(opposite) <= 0) {//compareTo，当两串同索引位置上的字符相等，会自动匹配后面的字符
				res.append(s.charAt(0));
				s = s.substring(1);//别忘记逐渐缩小串
			} else {
				res.append(opposite.charAt(0));
				opposite = opposite.substring(1);
			}
			if (res.length() % 80 == 0) {//根据题目要求，字符满80个就换行
				System.out.println(res.substring(count * 80, (count + 1) * 80));
				count++;
			}
		}
		if (res.length() > count * 80) {//也要考虑剩下的余数部分
			System.out.println(res.substring(count * 80));
		}
	}
}
